/**
 * 889. 根据前序和后序遍历构造二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
 */
public class Solutions_889 {
    public static void main(String[] args) {
//        int[] pre = {1, 2, 4, 5, 3, 6, 7};
//        int[] post = {4, 5, 2, 6, 7, 3, 1};  // output: {1, 2, 3, 4, 5, 6, 7}

        int[] pre = {8, 6, 1, 9, 10, 3, 4, 7, 2, 5};
        int[] post = {9, 1, 6, 2, 7, 4, 3, 5, 10, 8};
        // output: {8, 6, 10, 1, null, 3, 5, 9, null, 4, null, null, null, null, null, 7, null, 2}

//        TreeNode result = constructFromPrePost(pre, post);
        TreeNode result = constructFromPrePost2(pre, post);
        System.out.println(MyTreeNodeUtils.serialize(result));
    }

    /**
     * 解法二：递归
     */
    public static TreeNode constructFromPrePost2(int[] pre, int[] post) {
        return buildTree(pre, post, 0, 0, pre.length);
    }

    /**
     * 构造二叉树
     * @param preIdx pre 起始索引
     * @param postIdx post 起始索引
     * @param len 根节点个数
     * @return
     */
    public static TreeNode buildTree(int[] pre, int[] post, int preIdx, int postIdx, int len) {
        if (len == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[preIdx++]);
        if (len == 1) {
            // 没有子节点，直接返回
            return root;
        }
        int i = postIdx;
        for (; i < postIdx + len; i++) {
            if (post[i] == pre[preIdx]) {
                break;
            }
        }
        // root 的左子节点，共有 count 个子节点
        int count = i - postIdx + 1;
        // 构造左子树
        root.left = buildTree(pre, post, preIdx, postIdx, count);
        // 构造右子树（共有 len - count - 1 个节点）
        root.right = buildTree(pre, post, preIdx + count, postIdx + count, len - count - 1);
        return root;
    }


    private static int preIdx = 0;
    private static int postIdx = 0;
    /**
     * 解法一：递归
     */
    public static TreeNode constructFromPrePost(int[] pre, int[] post) {
        // 根节点
        TreeNode root = new TreeNode(pre[preIdx++]);
        if (root.val != post[postIdx]) {
            // 构建左子树
            root.left = constructFromPrePost(pre, post);
        }
        if (root.val != post[postIdx]) {
            // 构建右子树
            root.right = constructFromPrePost(pre, post);
        }
        // 一个节点构造完成，后序遍历索引加 1
        postIdx ++;
        return root;
    }
}
